package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _78二叉树中的最大路径和
 * @description
 * @date 2023/08/02 15:34
 * <p>
 * ******************************************************
 */
public class _78二叉树中的最大路径和 {

    int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        postOrder(root);
        return res;
    }

    private int postOrder(TreeNode root) {
        if (null == root) {
            return 0;
        }
        // 小于0就不用管
        int left = Math.max(postOrder(root.left), 0);
        int right = Math.max(postOrder(root.right), 0);
        int max = Math.max(left, right);
        int value = root.val + left + right;
        res = Math.max(value, res);
        return max + root.val;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
